/* Minimum Diameter Spanning Tree Problem.
 * Felipe Osorio Thome 7696409 <f.o.thome@gmail.com>, 2014. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define FALSE 0
#define TRUE 1
#define MAX_VERTICES 1000
#define MAX_WEIGHT 100000
#define INF 1000000

typedef struct
{
    int vertex;
    int dist;
} PAIR;

typedef struct
{
    int source;
    int target;
    int weight;
} EDGE;

void *xcalloc(unsigned long int, int);
int *floyd_warshall(int, int, int *);
int compare(const void *, const void *);
int min(int, int);

int main(int argc, char *argv[])
{
    /* n: number of vertices.
     * m: number of edges.
     * a, b: edges' vertices.
     * 2 <= n <= 1000.
     * (n - 1) <= m <= (n * (n - 1)) / 2.
     * 1 <= a, b <= n.
     * 1 <= w <= 10e5. */

    /* Input data. */
    int n, m;
    int a, b, w;

    /* Problem related variables. */
    float diameter = INF;
    int *adj_matrix = NULL, *d = NULL, *L = NULL;
    EDGE *edges = NULL;

    /* Misc variables. */
    int verify, i, j, k;

    /* Reading number of vertices and number of edges. */
    scanf("%d %d", &n, &m);
    verify = n < 2 || n > MAX_VERTICES ? FALSE :
             m < (n - 1) || m > (n * (n - 1)) / 2 ? FALSE : TRUE;
    if(!verify) exit(EXIT_FAILURE);

    /* Preparing adjacency matrix.
     * Must exist a path between all vertices except the main diagonal.*/
    adj_matrix = (int *)xcalloc(n * n, sizeof(int));
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            adj_matrix[i * n + j] = INF;
        }
        adj_matrix[i * n + i] = 0;
    }

    /* Reading edges. */
    edges = (EDGE *)xcalloc(m, sizeof(EDGE));
    for(i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &w);
        verify = a < 1 || a > n ? FALSE :
                 b < 1 || b > n ? FALSE :
                 w < 1 || w > MAX_WEIGHT ? FALSE : TRUE;
        if(!verify) exit(EXIT_FAILURE);

        adj_matrix[((a - 1) * n) + b - 1] = w;
        adj_matrix[((b - 1) * n) + a - 1] = w;

        edges[i].source = a - 1;
        edges[i].target = b - 1;
        edges[i].weight = w;
    }

    /* Calculating the shortest paths. */
    d = floyd_warshall(n, m, adj_matrix);

    /* Calculating the dominating pairs. */
    L = (int *)xcalloc(n * n, sizeof(int));
    PAIR *aux = (PAIR *)xcalloc(n, sizeof(PAIR));
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            aux[j].dist = d[i * n + j];
            aux[j].vertex = j;
        }
        qsort((void *)aux, n, sizeof(PAIR), compare);

        for(j = 0; j < n; j++)
        {
            L[i * n + j] = aux[j].vertex;
        }
    }

    /* Calculating the absolute center. */
    for(i = 0; i < m; i++)
    {
        int s = edges[i].source, t = edges[i].target;
        int w = edges[i].weight;
        float global_min, x, y;

        s = s * n;
        t = t * n;

        /* This will give us a global minimum for a certain edge. */
        global_min = d[s + L[s + 0]];
        for(j = 1, k = 0; j < n; j++)
        {
            if (d[t + L[s + k]] < d[t + L[s + j]])
            {
                x = (float) (d[t + L[s + k]] - d[s + L[s + j]] + w) / 2;
                y = x + d[s + L[s + j]];

                if(y < global_min) global_min = y;

                k = j;
            }
        }

        if(global_min < diameter) diameter = global_min;
    }

    printf("%.2f\n", diameter);

    return 0;
}

int *floyd_warshall(int n, int m, int *adj_matrix)
{
    int *g = NULL;
    int i, j, k;

    g = (int *)xcalloc(n * n, sizeof(int));
    memcpy(g, adj_matrix, sizeof(int) * n * n);

    for(k = 0; k < n; k++)
    {
        for(i = 0; i < n; i++)
        {
            if(k != i)
            {
                for(j = 0; j < i; j++)
                {
                    g[i * n + j] = min(g[i * n + j], g[i * n + k] + g[k * n + j]);
                    g[j * n + i] = g[i * n + j];
                }
            }
        }
    }

    return g;
}

int compare(const void *a, const void *b)
{
    const PAIR *elem1 = a;
    const PAIR *elem2 = b;

    if(elem1->dist > elem2->dist)
    {
        return -1;
    }
    else if(elem1->dist < elem2->dist)
    {
        return 1;
    }
    else
    {
        return 0;

    }
}

int min(int a, int b)
{
    return a <= b ? a : b;
}

void *xcalloc(unsigned long int num, int size)
{
    void *ptr = NULL;
    ptr = calloc(num, size);
    if(!ptr)
    {
        fprintf(stderr, "%s: %d: %s\n", __FILE__, __LINE__, strerror(errno));
        exit(EXIT_FAILURE);
    }
    return ptr;
}
